package seqlist;

/**
 * @author yuisama
 * @date 2022/04/25 19:16
 **/
public class DoubleLinkedList {
    // 有效节点的个数
    private int size;
    // 当前头节点
    private DoubleNode head;
    // 当前尾节点
    private DoubleNode tail;
    // 在双向链表的头部插入新节点
    public void addFirst(int val) {
        // 首先创建一个新节点
//        DoubleNode node = new DoubleNode(val);
        // 这个新节点就是以后的头节点
        // 构造方法就是为对象属性进行初始化的！
        DoubleNode node = new DoubleNode(null,val,head);
        if (tail == null) {
            tail = node;
        }else {
            head.prev = node;
        }
        // 对于头插来说，最终无论链表是否为空。head = node
        head = node;
        size ++;
    }

    public void addLast(int val) {
        // 这个节点就是插入后的尾节点
        DoubleNode node = new DoubleNode(tail,val,null);
        if (tail == null) {
            head = node;
        }else {
            tail.next = node;
        }
        tail = node;
        size ++;
    }

    public void add(int index,int val) {
        // 1.边界
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }
        if (index == 0) addFirst(val);
        else if (index == size) addLast(val);
        else {
            // 中间位置插入
            DoubleNode prev = node(index - 1);
            DoubleNode next = prev.next;
            DoubleNode cur = new DoubleNode(prev,val,next);
            prev.next = cur;
            next.prev = cur;
            size ++;
        }
    }
    // TODO
    public int get(int index) {
        return 0;
    }
    // TODO
    public int set(int index,int newVal) {
        return 0;
    }

    public void removeIndex(int index) {
        if (index < 0 || index >= size) {
            System.err.println("remove index illegal!");
            return;
        }
        DoubleNode cur = node(index);
        unlink(cur);
    }

    public void removeFirst() {
        removeIndex(0);
    }

    public void removeLast() {
        removeIndex(size - 1);
    }

    /**
     * 删除出现第一个值为val的结点
     * @param val
     */
    public void removeValueOnce(int val) {
        for (DoubleNode x = head;x != null;x = x.next) {
            if (x.val == val) {
                unlink(x);
                // x.next就断开了
                break;
            }
        }
    }
    public void removeAllValue(int val) {
        for (DoubleNode x = head;x != null;){
            if (x.val == val) {
                // x就是待删除的结点
                // 暂存后继结点的地址
                DoubleNode successor = x.next;
                unlink(x);
                x = successor;
            }else {
                x = x.next;
            }
        }
    }



    /**
     * 删除当前双向链表中的node节点
     * @param node
     */
    private void unlink(DoubleNode node) {
        // 1.前空后空
        // 2.前不空后空
        // 3.前不空后不空
        // 4.前空后不空
        DoubleNode prev = node.prev;
        DoubleNode successor = node.next;
        // 1.先处理node的前半部分
        if (prev == null) {
            head = successor;
        }else {
            // 前驱不为空的情况
            prev.next = successor;
            node.prev = null;
        }
        // 2.再处理后半部分的情况
        if (successor == null) {
            tail = prev;
        }else {
            successor.prev = prev;
            node.next = null;
        }
        size --;
    }

    /**
     * 根据索引值去找到对应的节点
     * @param index
     * @return
     */
    private DoubleNode node(int index) {
        DoubleNode x = null;
        if (index < size / 2) {
            x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
        }else {
            x = tail;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
        }
        return x;
    }


    public String toString() {
        String ret = "";
        for (DoubleNode x = head;x != null;x = x.next) {
            ret += x.val;
            ret += "->";
        }
        ret += "NULL";
        return ret;
    }
}
// 双向链表的节点类
class DoubleNode {
    // 前驱节点
    DoubleNode prev;
    // 当前节点值
    int val;
    // 后继节点
    DoubleNode next;
    // alt + insert

    public DoubleNode() {}

    public DoubleNode(int val) {
        this.val = val;
    }

    public DoubleNode(DoubleNode prev, int val, DoubleNode next) {
        this.prev = prev;
        this.val = val;
        this.next = next;
    }
}